package Algorithm.Othes;
//https://leetcode-cn.com/problems/shortest-completing-word/
public class Leetoce758 {
    class Solution {
        public String shortestCompletingWord(String licensePlate, String[] words) {
            int[] cnt = new int[26];
            for (int i = 0; i < licensePlate.length(); ++i) {
                char ch = licensePlate.charAt(i);
                if (Character.isLetter(ch)) {
                    ++cnt[Character.toLowerCase(ch) - 'a'];
                }
            }
            int idx = -1;
            for (int i = 0; i < words.length; ++i) {
                int[] c = new int[26];
                for (int j = 0; j < words[i].length(); ++j) {
                    char ch = words[i].charAt(j);
                    ++c[ch - 'a'];
                }
                boolean ok = true;
                for (int j = 0; j < 26; ++j) {
                    if (c[j] < cnt[j]) {
                        ok = false;
                        break;
                    }
                }
                if (ok && (idx < 0 || words[i].length() < words[idx].length())) {
                    idx = i;
                }
            }
            return words[idx];
        }
    }

}
